package com.aqie.medium.doublePointer;

/**
 * 75 颜色分类(原地排序 012顺序)
 *
 */
public class SortColors {
    /**
     * 桶排序
     *
     * @param nums
     */
    public void sortColors(int[] nums) {
        int[] result = new int[3];
        for (int num : nums) {
            int index = num % 3;
            result[index] = result[index] + 1;
        }
        int i = 0, j = 0;
        while (i < 3) {
            int count = result[i];
            while (count > 0) {
                nums[j++] = i;
                count--;
            }
            i++;
        }
    }

    /**
     * 三指针
     * @param nums
     */
    public void sortColors2(int[] nums) {
        int i = 0;
        int left = 0;
        int right = nums.length - 1;
        while (i <= right) {
            while (nums[i] == 2 && i < right) {
                int tmp = nums[i];
                nums[i] = nums[right];
                nums[right] = tmp;
                right--;
            }
            while (nums[i] == 0 && i > left) {
                int tmp = nums[i];
                nums[i] = nums[left];
                nums[left] = tmp;
                left++;
            }
            i++;
        }
    }

    // todo
    public void sortColors3(int[] nums){
        int low = 0, high = nums.length - 1;
        while (low < nums.length && nums[low] == 0) low++;

        while (high > low && nums[high] == 2) high--;

        for (int i =0; i < nums.length;i++){
            if (i > low && nums[i] == 0){
                if (nums[i] == nums[low]) return;
                nums[i] ^= nums[low];
                nums[low] ^= nums[i];
                nums[i] ^= nums[low];
                i--; low++;
            }else if (i < high && nums[i] == 2){

                if (nums[i] == nums[high]) return;
                nums[i] ^= nums[high];
                nums[high] ^= nums[i];
                nums[i] ^= nums[high];
                i--;high--;
            }
        }
    }
}

